package leetcode.f1t100;

/**
 * 字符串数字相乘
 * https://leetcode.com/problems/multiply-strings/
 *
 * @Author lichongxiao
 * @Date 2022/10/20 20:09
 */
public class Q43_MultiplyStrings {
    public String multiply(String num1, String num2) {
        char[] c1 = num1.toCharArray();
        char[] c2 = num2.toCharArray();
        int[] ansInts = new int[c1.length + c2.length];
        for (int i = c1.length - 1; i >= 0; i--) {
            for (int j = c2.length - 1; j >= 0; j--) {
                int temp = (c1[i] - '0') * (c2[j] - '0') + ansInts[i+j+1];
                ansInts[i+j] += temp / 10;
                ansInts[i+j+1] = temp % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int ansInt : ansInts){
            if(ansInt > 0 || sb.length() > 0){
                sb.append(ansInt);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

    public String multiply1(String num1, String num2) {
        String ans = "0";
        String step = "";
        for (int i = num2.length() - 1; i >= 0; i--) {
            ans = add(ans, multiplyOne(num1, num2.charAt(i)) + step);
            step += "0";
        }
        while (ans.length() > 0 && ans.charAt(0) == '0') {
            ans = ans.replaceFirst("0", "");
        }
        return ans.isEmpty() ? "0" : ans;
    }

    private String multiplyOne(String num1, char one) {
        if (one == '0') {
            return "0";
        }
        int times = one - '0';
        String ans = "0";
        for (int i = 0; i < times; i++) {
            ans = add(ans, num1);
        }
        return ans;
    }

    private String add(String num1, String num2) {
        if (num1.length() > num2.length()) {
            String num3 = num2;
            num2 = num1;
            num1 = num3;
        }
        boolean hflag = false;
        StringBuilder sb = new StringBuilder();
        int index1 = num1.length() - 1, index2 = num2.length() - 1;
        while (index1 >= 0) {
            int temp = (num1.charAt(index1) - '0') + (num2.charAt(index2) - '0');
            if (hflag) {
                temp++;
            }
            sb = sb.insert(0, (char) (temp % 10 + '0'));
            hflag = temp > 9;
            index1--;
            index2--;
        }
        while (index2 >= 0) {
            int temp = (num2.charAt(index2) - '0');
            if (hflag) {
                temp++;
            }
            sb = sb.insert(0, (char) (temp % 10 + '0'));
            hflag = temp > 9;
            index2--;
        }
        if (hflag) {
            sb.insert(0, '1');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Q43_MultiplyStrings bean = new Q43_MultiplyStrings();
        System.out.println(bean.add("999", "1"));
        System.out.println(bean.multiplyOne("999", '2'));
        System.out.println(bean.multiply("99", "11"));
        System.out.println(bean.multiply("0", "256"));
    }
}
